\section{Problema 2}

\subsection{Enunciado}

Como estamos acostumbrados en nuestro pa\'is corren tiempos dif\'iciles econ\'omicamente. Es por esto que el gobierno 
ha decidido optimizar la iluminaci\'on de las rutas, pero manteniendo la ”seguridad”.\\
Hasta ahora manten\'ia siempre prendida la luz de todas las rutas. Ahora se busca poder apagar algunas luces, pero
manteniendo la posibilidad de llegar de un punto a otro por un camino iluminado.\\ \\

Teniendo en cuenta que el costo del metro de ruta iluminado por d\'ia es de 1 peso. Se quiere averiguar cu\'anto es la
cantidad m\'axima que se puede ahorrar por d\'ia manteniendo la seguridad. Las rutas son doble mano. \\ \\

Analizar la complejidad temporal usando el modelo uniforme y expresarla en funci\'on de $n$, $m$. Se debe encontrar un
algoritmo con complejidad menor estricto que $O(n * m)$.


\subsection{Modelado}
Para encontrar las solucion del problema se modelara el pa\'is con un grafo pesado donde los vertices de dicho grafo representan las ciudades y las aristas a las rutas que las unen, los pesos de las aristas son el resultado del producto de la longitud de la ruta que representan y su costo de mantenimiento.
Se nos pide averiguar cuanto es el monto maximo que se puede ahorrar cortando la iluminacion de algunas rutas con la condici\'on de que se pueda llegar de cualquier punto a otro. 
La soluci\'on esta est\'a en obtener el peso de un Arbol Generador Minimo(AGM) dado que el grafo obtenido es conexo(lo que nos permite llegar de un punto $a$ a otro $b$).

\subsection{Correctitud}
Soluci\'on del problema $\Rightarrow$ soluci\'on modelo.\\
La soluci\'on del problema esta en elegir un subconjunto del conjunto de rutas del pa\'is tal que el gasto sea minimo y que se pueda llegar de un extremo a otro. Como el gasto va a ser minimo y el pa\'is se va a mantener conectaado, su representacion en la solucion del modelo sera un AGM, dado que este minimiza el peso del conjunto de aristas del grafo de salida manteniendolo conexo.
\\ \\
Soluci\'on del modelo $\Rightarrow$ soluci\'on del problema.\\
La soluci\'n del modelo es un AGM del grafo G que representa al problema. Como el arbol es conexo, las ciudades a las que representan lo vertices van a tener un camino para llegar a cualquier otro punto del pa\'is, ademas como el peso del \'arbol es menor o igual que cualquier subgrafo conexo de G, este minimiza el gasto del problema ya que las aristas del \'arbol representan a las rutas que van a quedar iluminadas pudiendo llegar de un punto a otro.

%%%%%%%%%%%%%%
\subsection{Pseudoc\'odigo}
\begin{algorithm}[H]
\caption{Algoritmo principal}
\begin{algorithmic}[1]
\STATE leer(n, m)
\STATE $V(G) $ $\leftarrow$ $\{ v_{0}, ..., v_{n-1} \}$
\STATE $E(G) $ $\leftarrow$ $\emptyset$
\FOR{$i$ de 1 hasta m}
	\STATE leer(x,y,z)
	\STATE $E(G) $ $\leftarrow$ $E(G) \cup \{ (x,y)\} $ de peso $z$
\ENDFOR
\RETURN peso(G) - pesoAGM(G)
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{pesoAGM(Grafo $G = (V,E)$)}
\begin{algorithmic}[1]
\REQUIRE $ G $ conexo y con pesos en las aristas
\STATE
\STATE $E^\prime$ Ordenar $E(G)$ de forma creciente
\STATE
\STATE CC $\leftarrow$ vector de $|V|$ elementos
\STATE Ranks $\leftarrow$ vector de $|V|$ elementos
\STATE cantComponentes $\leftarrow$ $|V|$
\STATE pesoAGM $\leftarrow$ 0
\FOR{ $i$ de 0 hasta $|V|-1$ }
	\STATE CC[i] $\leftarrow$ $v_{i}$
	\STATE Ranks[i] $\leftarrow$ 0
\ENDFOR
\STATE i $\leftarrow$ 0
\WHILE{(cantComponentes $>$ 1) $\wedge$ (i $<$ $E^\prime$) }
	\STATE $e_{i} = (u,v)$
	\STATE $p$ $\leftarrow$ $l(e)$
	\STATE distinguidoU $\leftarrow$ Find(u)
	\STATE distinguidoV $\leftarrow$ Find(v)
	\IF{distinguidoU != distinguidoV}
		\STATE Union(distinguidoU,distinguidoV,CC)
		\STATE cantComponentes--
		\STATE pesoAGM $\leftarrow$ pesoAGM + p
	\ENDIF
		\STATE i $\leftarrow$ i + 1
\ENDWHILE
\RETURN pesoAGM
\end{algorithmic}
\end{algorithm}


\begin{algorithm}[H]
\caption{Find($u$)}
\begin{algorithmic}
\STATE $u^\prime$ $\leftarrow$ $u$
\WHILE{padre($u^\prime$) $\neq$ $u^\prime$}
	\STATE $u^\prime$ $\leftarrow$ padre($u^\prime$)
\ENDWHILE
\RETURN $u^\prime$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{Union($u$,$v$)}
\begin{algorithmic}
\IF{ $rank$($u$) $>$ $rank$($v$)}
	\STATE padre($v$) $\leftarrow$ $u$
\ELSE
	\IF{ $rank$($v$) $>$ $rank$($u$)} 
		\STATE padre($u$) $\leftarrow$ $v$
	\ELSE
		\STATE padre($v$) $\leftarrow$ $u$
		\STATE rank($u$) $\leftarrow$ rank($u$) $+1$
	\ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}

\subsection{Análisis de Complejidad}
\subsubsection{Elecci\'on de la estructura}
Para representar el Grafo se hizo uso del sistema de clases de C++, en ella la cantidad de nodos y aristas se representan con un entero sin signo, un vertice pertenece al grafo si este es menor o igual que la cantidad de vertices que indica la estructura. El tiempo de creacion del grafo sin aristas toma tiempo  constante ya que se inicializan variables primitivas.
\\

Para representar las aristas en el grafo se hizo uso de la estructura $vector$ que proporciona la biblioteca STL, el costo de creaci\'on sin par\'ametro\footnote{\url{http://www.cplusplus.com/reference/stl/vector/vector/}} es constante, y el costo de inserci\'on\footnote{\url{http://www.cplusplus.com/reference/stl/vector/push_back/}} de elementos es constante amortizado (que en nuestro an\'alisis de complejidad, es constante). Se prefiri\'o esta estructura dado que el algoritmo de Kruskal toma las aristas de acuerdo a su peso en forma creciente, as\'i podemos usar la funci\'on $sort$\footnote{\url{http://www.cplusplus.com/reference/stl/list/sort/}} de complejidad $O(n * log(n))$.
\\

ACLARACI\'ON: contrario a la notaci\'on habitual, se representa con las letras\\
\textbf{m}: cantidad de nodos de un grafo \\
\textbf{n}: cantidad de aristas de un grafo\\
Pero seguir la usada por el enunciado es muy confuso, as\'i que optamos por referirnos con $|V|$ y $|E|$, respectivamente \\


El programa se divide en 2 etapas

\begin{enumerate}
	\item Creaci\'on del Grafo (Algoritmo principal)
	\item Resolucion del problema (pesoAGM)
\end{enumerate}

A continuacion pasamos a explicar la complejidad de cada paso.

\subsubsection{Crear grafo}
Se procede a la creaci\'on del grafo con $|V|$ v\'ertices (implementado sobre un vector de tamaño $|V|$) y un conjunto de aristas vac\'io (vector de tamaño 1), que tiene complejidad $O(|V|)$ y constante ${c}_{1}$, respectivamente (V\'ease aclaraci\'on sobre la STL).\\
Luego el ciclo de la funci\'on procede a agregar las $|E|$ aristas. Agregar una arista (\textit{push\_back}) toma tiempo amortizado constante $c_2$, por lo que agregar $|E|$ aristas toma $|E| $ $O(c_2) = O(c_2 |E|) \in O(|E|)$.\\
\\
Complejidad : $O(|V|+|E|)$ = $O(|E|)$  (m\'as adelante se explica por qu\'e $|E|$ acota a $|V|$ )

\subsubsection{Resolucion del problema}

La \'ultima l\'inea del algoritmo principal devuelve el resultado de una resta. El peso del grafo es una variable primitiva que se actualizaba con costo $O(1)$ cada vez que se agregaba una arista. La resta entre tipos de datos primitivos es $O(1)$.\\
La complejidad de esa l\'inea recae en el algoritmo que obtiene el peso del AGM.\\
\\
El algoritmo elegido para encontrar un AGM es el algoritmo de Kruskal, con las siguientes caracter\'isticas en su implementaci\'on:\\

\begin{enumerate}
	\item Se ordena de forma creciente seg\'un su peso, las aristas del grafo. Garantiza obtener la de m\'inimo peso en cada iteraci\'on si se la recorre linealmente. 
	\item Algoritmos de Union \& Find para detectar potenciales ciclos (al insertar una arista) y para unir componentes conexas. Para garantizar la cota de complejidad se opt\'o por optimizarlo con \textit{union-by-rank}
\end{enumerate}


Teniendo en cuenta lo dicho antes, analizamos ahora las complejidades del algoritmo de Kruskal:\\
\begin{enumerate}
	\item Ordenar un vector de aristas (estructura de cantidad acotada de variables primitivas) de $|E|$ elementos tiene complejidad $O(|E| log (|E|)) = O(|E| log (|V|))$ comparaciones de costo $O(1)$, como lo asegura la funci\'on \textit{sort}.\\
\\Justificaci\'on: Por el modelo usado (grafos), vale $|E| \leq |V|(|V|-1)/2$. Es decir, $|E|$ es del orden de $|V|^{2}$, por lo tanto:\\
$T_{ordenar}(|V|,|E|)$  $\in$  $O(|E| log(|V|^{2}))$ = $O(|E|*2*log(|V|))$ = $O(|E| log(|V|))$ \\
	\item Pasos 4 y 5.  Crear vectores de $|V|$ elementos es $O(|V|)$  (por constructor de vector de la STL)
	\item Pasos 6 y 7. Asignaci\'on de tipos de datos primitivos: $O(1)$
	\item Inicializar dos vectores de $|V|$ elementos. Se realizan $|V|$ asignaciones con costo $O(1)$. La complejidad es $O(|V|)$
	\item Asignaci\'on de variable primitiva, $O(1)$\\
	\\ Union and Find:	
	\item Tiene que unir las $|V|$ componentes conexas, una a la vez, hasta que quede una sola. En total har\'a $|V|-1$ uniones (condicion  \textit{cantComponentes} $> 1$.
	\item Recorre a lo sumo $|E|$ aristas (condicion $ i < |E|$), que es mayor o igual que la cantidad de uniones. Por lo tanto, el ciclo tiene en el peor caso $|E|$ pasos. 
	\item En cada iteraci\'on, se realizan operaciones y asignaciones de tipos primitivos de datos ($p$, $distinguidoU$, $distinguidoV$, $cantComponentes$, $pesoAGM$, $i$) que son del orden de $O(1)$
	\item La complejidad de \textit{Union} es $O(1)$ porque realiza comparaciones y asignaciones entre enteros.
	\item La heur\'istica \textit{Union by Rank} asegura que una secuencia de $|E|$ llamadas a \textit{Find} no tendr\'a complejidad mayor que $O(|E|* log|V|)$ \footnote{Cormen,Thomas . "Introduction to Algorithms. 2nd", 21.3 Disjoint-set Forests}
	\item En conclusi\'on, el ciclo tiene complejidad $|E|*O(1)+ O(|E|log(|V|))$ = $O(|E| log(|V|))$
\end{enumerate}


\subsubsection{Complejidad total del algoritmo}

$$T_{final}(|V|,|E|) \in O(|E| + |E| log(|V|)) \in O(|E| log(|V|))$$\\
que es estrictamente mejor que $O(|E| * |V|)$

\subsection{Mediciones}

La complejidad del algoritmo es $O(|E| log (|V|))$. Debido a la funci\'on logaritmo, la cantidad de v\'ertices no es algo que afecte demasiado.
No as\'i la cantidad de aristas, la cual adem\'as se encuentra acotada entre funciones de $|V|$

\subsubsection{Mejor Caso}
Ocurre cuando la cantidad de aristas es m\'inima. Si el problema garantiza que el grafo asociado del modelo ser\'a conexo, el mejor caso ocurre cuando dicho grafo es un \'arbol. \'Esto es, cuando $|E| = |V| - 1$ \\

\mifig{problema2/mejor}{Mejor Caso}
%\input{problema2/mejor.tex} \\

La complejidad es del orden de $O(|V| log (|V|))$

\subsubsection{Peor Caso}
Por otro lado, si la cantidad de aristas es m\'axima, se llega al peor caso. Y ocurre cuando $|E| = |V| (|V| - 1)$  \\
Es decir, cuando el grafo es un \textit{grafo completo}.

\mifig{problema2/peor}{Peor Caso}
%\input{problema2/peor.tex} \\

Por lo tanto, la complejidad del algoritmo es prácticamente $O(|V|^{2} log (|V|))$

\subsubsection{Casos aleatorios}
Todos los dem\'as casos se encuentran entre el mejor y el peor caso. Para una cantidad fija de $|V|$, la cantidad de aristas est\'a en el rango $ |V| - 1 \leq |E| \leq |V| (|V| - 1)$\\

Para corroborar emp\'iricamente la cota de complejidad del algoritmo, dado que depende de dos variables, fijaremos una mientras la otra act\'ua como variable.\\

Si $|V|$ es constante, la funci\'on de complejidad temporal depende s\'olo de la variable $|E|$. Pertenece a $O(|E| log (k))$ = $O(|E|)$ , k constante. \\

\mifig{problema2/vfijo}{Casos Aleatorios - $|V|$ Fijo}
%\input{problema2/vfijo.tex} \\

Si $|E|$ es constante, la funci\'on de complejidad temporal depende s\'olo de la variable $|V|$. Pertenece a $O(k log (|V|))$ = $O(log|V|)$ , k constante. \\

\mifig{problema2/efijo}{Casos Aleatorios - $|E|$ Fijo}
%\input{problema2/efijo.tex} \\

En cualquiera de los dos casos, $|E|$ y $|V|$ deben ser consistentes con el rango definido anteriormente:\\
$$ |V| - 1 \leq |E| \leq |V| (|V| - 1)$$

\newpage
